package org.maylove.wuziqi.game;

public class GameNumTree {
    private Integer[] node;
    private Integer size;
    public GameNumTree(Integer size) {
        node = new Integer[size * 4];
        this.size = size;
        initRoom(1, 1, size);
    }

    private void initRoom(int u, int l, int r) {
        if(l == r) {
            node[u] = 1;
            return;
        }
        int mid = (l + r) / 2;
        int ls = u * 2;
        int rs = ls + 1;
        initRoom(ls, l, mid);
        initRoom(rs, mid+1, r);
        node[u] = node[ls] + node[rs];
    }

    private int query(int u, int l, int r) {
        if(l == r) return l;
        int mid = (l + r) / 2;
        int ls = u * 2;
        int rs = ls + 1;
        if(node[ls] != 0) return query(ls, l ,mid);
        else return query(rs, mid+1, r);
    }

    private void add(int u, int l, int r, int x, int y) {
        node[u] += y;
        if(l == r) return;
        int mid = (l + r) / 2;
        int ls = u * 2;
        int rs = ls + 1;
        if(x <= mid) add(ls, l, mid, x, y);
        else add(rs, mid+1, r, x, y);
    }

    public Integer getRoom() {
        if(node[1] == 0) return -1;
        int res = query(1, 1, size);
        add(1, 1, size, res, -1);
        return res;
    }

    public void putRoom(int x) {
        add(1, 1, size, x, 1);
    }
}
